<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>text Justification</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="text-justification">text Justification</h1>
<h1 id="1-tushar-roy">1. tushar roy</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=RORuwHiblPc&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=23">https://www.youtube.com/watch?v=RORuwHiblPc&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=23</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/TextJustification.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/TextJustification.java</a></li>
</ul>
<p>本题规则和下面leetcode 68不一样，每一行的文本尽可能对齐，也就是每一行的平均长度尽可能一样，长度的方差最小。</p>
<ul>
<li>单词的间隔都是一个空格</li>
<li>求的是每行末尾的空格数的平方和最小。</li>
</ul>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp14.png" alt="dp14.png"></p>
<p>这个解法分成两步。 时间复杂度， 空间复杂度都是O(n^2)</p>
<ol>
<li>求第i个单词开头的可能line的末尾空格数的平方， 构建矩阵</li>
<li>根据矩阵来运算怎么把单词分行。</li>
</ol>
<p>具体看代码吧，第二步不是很好懂</p>
<pre><code class="language-java"><div><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">TextJustification</span> </span>{

    <span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">justify</span><span class="hljs-params">(String words[], <span class="hljs-keyword">int</span> width)</span> </span>{
        
        <span class="hljs-keyword">int</span> cost[][] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[words.length][words.length];
        
        <span class="hljs-comment">//next 2 for loop is used to calculate cost of putting words from</span>
        <span class="hljs-comment">//i to j in one line. If words don't fit in one line then we put</span>
        <span class="hljs-comment">//Integer.MAX_VALUE there.</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span> ; i &lt; words.length; i++){
            cost[i][i] = width - words[i].length();
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=i+<span class="hljs-number">1</span>; j &lt; words.length; j++){
                cost[i][j] = cost[i][j-<span class="hljs-number">1</span>] - words[j].length() - <span class="hljs-number">1</span>; 
            }
        }
        
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i &lt; words.length; i++){
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=i; j &lt; words.length; j++){
                <span class="hljs-keyword">if</span>(cost[i][j] &lt; <span class="hljs-number">0</span>){
                    cost[i][j] = Integer.MAX_VALUE;
                }<span class="hljs-keyword">else</span>{
                    cost[i][j] = (<span class="hljs-keyword">int</span>)Math.pow(cost[i][j], <span class="hljs-number">2</span>);
                }
            }
        }
        
        <span class="hljs-comment">//minCost from i to len is found by trying</span>
        <span class="hljs-comment">//j between i to len and checking which</span>
        <span class="hljs-comment">//one has min value</span>
        <span class="hljs-keyword">int</span> minCost[] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[words.length];
        <span class="hljs-keyword">int</span> result[] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[words.length];
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = words.length-<span class="hljs-number">1</span>; i &gt;= <span class="hljs-number">0</span> ; i--){
            minCost[i] = cost[i][words.length-<span class="hljs-number">1</span>];
            result[i] = words.length;
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=words.length-<span class="hljs-number">1</span>; j &gt; i; j--){
                <span class="hljs-keyword">if</span>(cost[i][j-<span class="hljs-number">1</span>] == Integer.MAX_VALUE){
                    <span class="hljs-keyword">continue</span>;
                }
                <span class="hljs-keyword">if</span>(minCost[i] &gt; minCost[j] + cost[i][j-<span class="hljs-number">1</span>]){
                    minCost[i] = minCost[j] + cost[i][j-<span class="hljs-number">1</span>];
                    result[i] = j;
                }
            }
        }
        <span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">int</span> j;
        
        System.out.println(<span class="hljs-string">"Minimum cost is "</span> + minCost[<span class="hljs-number">0</span>]);
        System.out.println(<span class="hljs-string">"\n"</span>);
        <span class="hljs-comment">//finally put all words with new line added in </span>
        <span class="hljs-comment">//string buffer and print it.</span>
        StringBuilder builder = <span class="hljs-keyword">new</span> StringBuilder();
        <span class="hljs-keyword">do</span>{
            j = result[i];
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> k=i; k &lt; j; k++){
                builder.append(words[k] + <span class="hljs-string">" "</span>);
            }
            builder.append(<span class="hljs-string">"\n"</span>);
            i = j;
        }<span class="hljs-keyword">while</span>(j &lt; words.length);
        
        <span class="hljs-keyword">return</span> builder.toString();
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span></span>{
        String words1[] = {<span class="hljs-string">"Tushar"</span>,<span class="hljs-string">"likes"</span>,<span class="hljs-string">"to"</span>,<span class="hljs-string">"write"</span>,<span class="hljs-string">"code"</span>,<span class="hljs-string">"at"</span>, <span class="hljs-string">"free"</span>, <span class="hljs-string">"time"</span>};
        TextJustification awl = <span class="hljs-keyword">new</span> TextJustification();
        System.out.println(awl.justify(words1, <span class="hljs-number">12</span>));
    }
}
</div></code></pre>
<h1 id="2-leetcode-68-text-justification">2. leetcode 68 text justification</h1>
<ul>
<li><a href="https://leetcode.com/problems/text-justification/">https://leetcode.com/problems/text-justification/</a></li>
</ul>
<p>文本按照maxWidth 进行排版</p>
<p>Note:</p>
<pre><code><code><div>A word is defined as a character sequence consisting of non-space characters only.
Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.
Example 1:

Input:
words = [&quot;This&quot;, &quot;is&quot;, &quot;an&quot;, &quot;example&quot;, &quot;of&quot;, &quot;text&quot;, &quot;justification.&quot;]
maxWidth = 16
Output:
[
   &quot;This    is    an&quot;,
   &quot;example  of text&quot;,
   &quot;justification.  &quot;
]
</div></code></code></pre>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> math

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">fullJustify</span><span class="hljs-params">(self, words: List[str], maxWidth: int)</span> -&gt; List[str]:</span>
        lines = []
        line = <span class="hljs-string">""</span>
        <span class="hljs-keyword">for</span> i,word <span class="hljs-keyword">in</span> enumerate(words):
            next_text = <span class="hljs-string">f"<span class="hljs-subst">{line}</span> <span class="hljs-subst">{word}</span>"</span> <span class="hljs-keyword">if</span> line <span class="hljs-keyword">else</span> word
            <span class="hljs-keyword">if</span> len(next_text) &gt; maxWidth:
                lines.append(line)
                line = word
            <span class="hljs-keyword">else</span>:
                line = next_text    
            <span class="hljs-keyword">if</span> i == len(words) - <span class="hljs-number">1</span>:
                lines.append(line)
            

        ans = []
        <span class="hljs-keyword">for</span> i,line <span class="hljs-keyword">in</span> enumerate(lines):
            words2 = line.split(<span class="hljs-string">" "</span>)
            <span class="hljs-keyword">if</span> i == len(lines) - <span class="hljs-number">1</span> <span class="hljs-keyword">or</span> len(words2) == <span class="hljs-number">1</span>:
                ans.append(line + <span class="hljs-string">" "</span> * (maxWidth - len(line)))
            <span class="hljs-keyword">else</span>:
                space_total = maxWidth - sum(map(<span class="hljs-keyword">lambda</span> x:len(x), words2))
                space_step, space_remain = divmod(space_total, len(words2)<span class="hljs-number">-1</span>)
                line2 = []
                <span class="hljs-keyword">for</span> word2 <span class="hljs-keyword">in</span> words2[:<span class="hljs-number">-1</span>]:
                    line2.append(word2)
                    line2.append(<span class="hljs-string">" "</span>*space_step)
                    <span class="hljs-keyword">if</span> space_remain:
                        line2.append(<span class="hljs-string">" "</span>)
                        space_remain -= <span class="hljs-number">1</span>
                line2.append(words2[<span class="hljs-number">-1</span>])
                ans.append(<span class="hljs-string">""</span>.join(line2))
        <span class="hljs-keyword">return</span> ans
</div></code></pre>

    </body>
    </html>